package greedy.跳跃问题;

public class leetcode45跳跃游戏2 {
    public static int jump(int[] nums) {
        int length = nums.length;
        // 记录当前步能跳到的最远距离
        int nextMaxD = 0;
        // 计算下一步能跳到的最远距离
        int maxD = 0;
        int step = 0;
        // 恰好跳到最后一步，step无需++
        for (int i = 0; i < length - 1; i++) {
            maxD = Integer.max(maxD, i + nums[i]);
            if (i == nextMaxD) {
                nextMaxD = maxD;
                step++;
            }
        }
        return step;
    }
}
